package com.atwy.graph.undirectedgraph;

import java.util.Arrays;

/**
 * @Author: 小王子火
 * @Date: 2022/3/5
 * 邻接矩阵构建的图
 * 1）一个一维数组存储图中顶点的信息
 * 2）一个二位数组存储图中顶点之间的邻接关系。
 * 存储顶点之间邻接关系的二位数组称为邻接矩阵
 *
 * 在实际中，如果顶点信息可以用数字表示，或者可以映射成数字
 * 则不需要一维数组来存储顶点信息了
 *
 * 优点：
 * 1、快速判断两顶点之间是否有边
 * 2、方便计算各顶点的度，（行->出度，列->入度）
 * 缺点：
 * 1、不便于增删顶点
 * 2、不便于访问所有邻接点
 * 3、空间复杂度高
 *
 */
public class MatrixGraph implements IGraph{
    /**
     * 顶点集合，类型可任意，在这里是String
     */
    private String vertexArray[];
    /**
     * 图对应的邻接矩阵
     */
    private int[][] edges;
    /**
     * 节点数、边数
     */
    int vexnum, edgenum;

    public MatrixGraph(int v) {
        // 初始化矩阵
        vexnum = v;
        edges = new int[v][v];
        vertexArray = new String[v];
    }

    /**
     * 添加顶点信息，返回顶点的下标
     *
     * @param vertex -1表示添加顶点失败
     */
    public int addVertex(String vertex) {
        if (vertex == null || vertex.trim().equals("")) {
            return -1;
        }
        for (int i = 0; i < vertexArray.length; i++) {
            if (vertexArray[i] == null) {
                vertexArray[i] = vertex;
            }
            if (vertex.equals(vertexArray[i])) {
                return i;
            }

        }
        return -1;
    }

    /**
     * 添加边
     *
     * @param v 顶点的下标
     * @param w 另一个顶点的下标
     */
    @Override
    public void addEdge(int v, int w) {
        edges[v][w] = edges[w][v] = 1;
        edgenum++;
    }

    /**
     * 通过下标获取顶点信息
     * @param index
     * @return
     */
    public String vertex(int index) {
        return (-1 < index && index < vexnum) ? vertexArray[index] : null;
    }

    /**
     * 返回v顶点的所有相邻顶点下标
     * @param v
     * @return
     */
    @Override
    public int[] adj(int v){
        int count = 0;
        for(int k : edges[v]){
            if(k==1){
                count++;
            }
        }
        int[] result = new int[count];
        int index = 0 ;
        for (int i = 0; i < edges[v].length; i++) {
            if(edges[v][i] == 1){
                result[index] = i;
                index++;
            }
        }
        return result;
    }
    @Override
    public int E() {
        return edgenum;
    }
    @Override
    public int V() {
        return vexnum;
    }

    public void showGraph() {
        for (int[] row : edges) {
            System.out.println(Arrays.toString(row));
        }
    }

}
